In most known digital mobile radio receivers, a Viterbi decoder is used. A Viterbi decoder is a so-called maximum likelihood decoder, which is generally used for decoding channel-coded, and in particular convolutionally coded, mobile radio signals. During channel coding, the transmitter adds redundant information to the symbols to be transmitted in order to increase the transmission reliability. During the transmission of a mobile radio signal, however, noise is superposed on the signal. The task of the receiver consists, therefore, in using the reception sequence to identify, from all possible transmission sequences, that transmission sequence which corresponds with maximum likelihood to the actual transmission sequence. This task is undertaken by the Viterbi decoder.
The coding specification used during the channel coding can be described by a corresponding trellis diagram. By calculating so-called metrics, the Viterbi decoder determines that path of the trellis diagram which has the largest or smallest path metric, depending on the respective configuration of the decoder. Using this path of the trellis diagram, the decoded sequence can then be determined and output.
The principles of Viterbi decoding will be briefly explained in more detail below.
FIG. 4 illustrates, by way of example, a trellis diagram with in each case four different states at the instants t . . . t+3, which correspond for example to the bit states “00”, “10”, “01” and “11”. Each symbol sequence is assigned a corresponding path in the trellis diagram. In this case, a path comprises a sequence of branches between two temporally successive states. Each branch symbolizes a state transition between two temporally successive states. For example, the upper branch preceding from a state corresponds to a reception symbol with the binary “0” and the lower branch proceeding from the same state corresponds to a reception symbol with the binary value “1”. Each of these state transitions to which a branch metric (BM) λt is allocated corresponds to a transmission symbol. The branch metric λt is defined as follows:λt=|yt′−rt2|
In this case, rt corresponds to the reception symbol at the instant t and γt′ corresponds to the transmission symbol expected as a function thereof at the instant t.
Furthermore, a path metric γt, is allocated to each path through the trellis diagram up to the instant or time step t.
The trellis diagram shown in FIG. 4 is, in particular, a trellis diagram with a so-called “butterfly” structure. This means that in each case, two states of a time step t+1 of the trellis program are allocated two states of the preceding time step t+1, whose branches in each case lead to the first-mentioned states of the time step t+1, in each case two branch metrics of the branches proceeding from different states being identical. Thus, for example, the states which are shown in FIG. 4 and to which the path metrics γt(1), γt(3), γt+1(2)and γt+1(3)are allocated form a “butterfly” structure of this type, the branch metric for the branch from the state with the path metric γt(1) to the state with the path metric γt+1(2)corresponding to the branch metric λt(3) of the branch from the state with the path metric γt(3) to the state with the path metric γt+1(3), while on the other hand the branch metric of the branch from the state with the path metric γt(1) to the state with the path metric γt+1(3) corresponds to the branch metric λt(1) of the branch from the state with the path metric γt(3) to the state with the path metric γt+1(2). In this case, γt(3) generally designates the path metric allocated to the state s in the time step t, while λt(3) designates the branch metric of the state transition corresponding to the signal s at the instant t.
The Viterbi decoder must then use an algorithm corresponding to the trellis diagram to determine that path which has the best path metric. As a rule, this is by definition the path having the smallest path metric.
Each path metric of a path leading to a specific state is composed of the path metric of a temporally preceding state and the branch metric of the branch leading from this preceding state to the specific state. The consequence of this is that not all of the possible paths and path metrics of the trellis diagram have to be determined and evaluated. Instead, for each state and for each time step of the trellis diagram, in each case that path which has the best path metric up to that instant is determined. Only this path, which is designated as a “survivor path”, and its path metric have to be stored. All other paths leading to this state can be disregarded. Accordingly, during each time step, there are a number of such survivor paths corresponding to the number of different states.
The above description makes it clear that the calculation of the path metric γt+1(3) depends on the path metrics of the preceding time step t, which are connected to the state via a branch. Accordingly, the calculation of the path metrics can be realized by a recursive algorithm which is undertaken by a so-called “Add Compare Select” unit (ACS unit) in a Viterbi decoder.
FIG. 5 illustrates the typical construction of a Viterbi decoder.
In addition to the ACS unit 2 with a memory or register 3, a branch metric unit (BMU) 1 and a survivor memory unit 4 are provided. The task of the branch metric unit is to calculate the branch metrics λt(3) which are a measure of the difference between a reception symbol and that symbol which engenders the corresponding state transition in the trellis diagram. The branch metrics calculated by the branch metric unit 1 are fed to the ACS unit 2 for determination of the optimal paths (survivor paths). The survivor memory unit 4 stores these survivor paths, so that finally decoding can be carried out using that survivor path that has the best path metric. The symbol sequence assigned to this path corresponds with maximum likelihood to the symbol sequence actually transmitted.
The ACS unit 2 comprises a plurality of processor elements. As a rule, each state of the trellis diagram is evaluated by a separate processor element. The task of each individual processor element is to select from two mutually competing paths (referred to as “competitor paths”) that lead to a state of the trellis diagram the path (referred to as the “survivor path”) having the best, i.e. smallest, path metric. The stored values for the survivor path leading to this state, together with its path metric, are then updated.
As is evident from the trellis diagram shown in FIG. 4, each state s, at the instant t+1, is connected to a corresponding preceding state via an upper branch and a lower branch. Consequently, in order to determine the survivor path corresponding to this state s, the path metric of the path leading to the state s via the upper branch must be compared with the path metric of the path leading to the state s via the lower branch, i.e. the task of each processor element consists in selecting, for the purpose of determining the survivor path with the path metric γt+1(3), either the path which leads via the preceding “upper” state with the path metric γt(u) and the “upper” branch with the branch metric γt(u) and whose path metric corresponds to the sum γt(u)+λt(u), or the path which leads via the “lower” state with the path metric γt(l) and the “lower” branch with the branch metric γt(l) and whose path metric corresponds to the sum γt(l)+λt(l).
Since each result γt(s) calculated for a state s in the time step t is at the same time the basis for the calculation of a path metric for a temporally succeeding state, the feedback, shown in FIG. 5, of the ACS unit 2 via the memory 3 is necessary, the calculated path metrics being buffered in the memory 3.
The structure of the memory 3 must be configured in accordance with the structure of the respective trellis diagram. During each symbol period, a number of path metrics corresponding to the number of states of the trellis diagram must be read from the memory 3 and written to the memory 3. For each butterfly of the trellis diagram, two states are processed simultaneously, so that two starting path metrics must be read from the memory 3 and two path metrics calculated therefrom must be written to the memory 3.
This gives rise, however, to the problem that the path metrics must not be overwritten before they have been read out.
In order to make this clearer, FIG. 6 illustrates a further trellis diagram with eight states. The trellis diagram has the butterfly structure already described, an exemplary butterfly being illustrated by broken lines and comprising the starting states St No. 1 and 5 and the destination states St+1 No. 2 and 3. Consequently, for the calculation of the path metrics of the destination states No. 2 and 3, the path metrics of the starting states No. 1 and 5 must first be read out.
This competition situation between the read-out operation and the write operation has led to a configuration of the memory 3 which is also known as “ping-pong” implementation in the literature. The memory 3 is subdivided into two memory banks, of which one is provided exclusively for read operations and the other is provided exclusively for write operations.
Although undesirable collisions are reliably avoided with the aid of this technique, the memory 3 must nonetheless have twice the size that would otherwise be necessary, since both memory banks each have to be able to store the path metrics of all states St and St+1.
A further problem associated with the storage of the path metrics is the mapping of the path metrics onto the memory, i.e. the assignment of the individual path metrics to the different memory addresses. According to the prior art, this mapping has to be chosen in such a way that different memory areas are used for the read and write operations of the path metricsin order to reliably avoid conflicts between the read and write operations.
The present invention provides a method for storing path metrics in a Viterbi decoder that can be realized with a lower memory requirement and that reliably prevents write/read conflicts.
The method for storing path metrics in a Viterbi decoder is on the principle of a time-variable trellis diagram and is particularly suitable for trellis diagrams having a butterfly structure and corresponding ACS units.
The method according to the invention requires just one memory and enables path metrics to be read from and stored in the same memory areas, i.e. the path metrics of corresponding destination states calculated on the basis of two starting path metrics are stored under the same memory address from which the two starting path metrics were previously read out. The size of the memory is independent of the respectively chosen degree of parallelism of the trellis and merely has to correspond to the product of the number of different trellis states and the number of bits per memory word. In particular, just one memory is necessary even when the path metrics for a plurality of processor elements are intended to be stored in combined form.
The invention requires a minimal amount of area and power consumption of the chip used for Viterbi decoding, since just one memory address is required for two path metrics. The invention is suitable both for feedforward codes, such as, for example, SDSL, and for feedback codes and allows the use of programmable Viterbi decoders, it being possible for the corresponding path metrics to be programmed in a simple manner for each butterfly.
The present invention is explained in more derail below using a preferred exemplary embodiment with reference to the accompanying drawing.